#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

class Solution {
public:

    // 413. 等差数列划分
    // https://leetcode.cn/problems/arithmetic-slices/
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        int ans = 0;

        for (int i = 2; i<n; ++i)
        {
            dp[i] = (nums[i]-nums[i-1] == nums[i-1]-nums[i-2]) ? dp[i-1] + 1 : 0;
            ans += dp[i];
        }
        return ans;
    }

    // 978. 最长湍流子数组
    // https://leetcode.cn/problems/longest-turbulent-subarray/
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        vector<int> f(n, 1);
        auto g = f;
        int ans = 1;

        for (int i = 1; i<n; ++i)
        {
            if (arr[i-1] < arr[i])
                f[i] = g[i-1] + 1;
            else if (arr[i-1] > arr[i])
                g[i] = f[i-1] + 1;
            ans = max(ans, max(f[i], g[i]));
        }

        return ans;
    }

    // 139. 单词拆分
    // https://leetcode.cn/problems/word-break/
    bool wordBreak(string s, vector<string>& wordDict) {

        unordered_set<string> hash(wordDict.begin(), wordDict.end());

        int n = s.size();
        vector<bool> dp(n+1);
        dp[0] = true;
        s = ' ' + s;

        for (int i = 1; i<=n; ++i)
        {
            for (int j = i; j>=1; --j)
            {
                if (dp[j-1] && hash.count(s.substr(j, i-j+1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};